package algotithm.acwing.bfs.test1101;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/3-17:51
 * @Title 1101. 献给阿尔吉侬的花束
 * @URL https://www.acwing.com/problem/content/1103/
 */
import java.util.*;
import java.io.*;

public class Main {

    /**
     * 搭配四个方位的，(-1,0) (0,-1) (1,0) (0,1)
     */

    private static int[] dx = {-1,0,1,0};
    private static int[] dy = {0,-1,0,1};
    /**
     *行和列
     */
    private static int row;
    private static int col;
    private static char[][] arr;
    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(reader.readLine());

        while (t-- > 0) {
            String[] num  = reader.readLine().split(" ");
            row = Integer.parseInt(num[0]);
            col = Integer.parseInt(num[1]);
            arr = new char[row][col];
            dp = new int[row][col];

            for (int i = 0; i < row; i++) {
                String num2 = reader.readLine();
                arr[i] = num2.toCharArray();
            }

            int[] start = new int[2];

            // 开始遍历
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (arr[i][j] == 'S') {
                        start = new int[]{i,j};
                    }
                }
            }
            writer.write(bfs(start) + "\n");
        }
        writer.flush();
        writer.close();
        reader.close();
    }


    public static String bfs(int[] st) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{st[0], st[1]});
        arr[st[0]][st[1]] = '#';
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            for (int i = 0; i < 4; i++) {
                // 向上下左右四个方位探索
                int x1 = x + dx[i];
                int y1 = y + dy[i];
                // 检查越界情况
                if (x1 < 0 || y1 < 0 || x1 >= row || y1 >= col || arr[x1][y1] == '#') {
                    continue;
                }
                // 如果遇到了，直接返回上一步的步数+1
                if (arr[x1][y1] == 'E') {
                    return dp[x][y] + 1 + "";
                }
                // 否则+1继续探索
                dp[x1][y1] = dp[x][y] + 1;
                arr[x1][y1] = '#';
                queue.add(new int[]{x1, y1});
            }
        }
        return "oop!";

    }

}
